#include <vector>
#include <iostream>

using namespace std;

struct Node{
	int val;
	Node * next;
	Node(): val(0), next(nullptr){}
	Node(int val): val(val), next(nullptr){}
	Node(int val, Node * next): val(val), next(next){}
};

class Solution{
public:
	Node * sort(Node * head){
		// Node * last = getLast(head);
		return split(head, nullptr);
	}
	
	Node * split(Node * left, Node * right){
		if (left == nullptr) {
            return left;
        }
        if (left->next == right) {
            left->next = nullptr;
            return left;
        }
		Node * mid = getMid(left, right);
		return merge(split(left, mid), split(mid, right));
	
	}
	
	Node * merge(Node * left, Node *right){
		Node * dummy = new Node(0);
		Node * tmp = dummy;
		Node * i;
		Node * j;
		while(i != nullptr && j != nullptr){
			if(i->val <= j->val){
				tmp->next = i;
				i = i->next;
			}else{
				tmp->next = j;
				j = j->next;
			}
			tmp = tmp->next;
		}
		
		if(i != left){
			tmp->next = i;
		}else if(j != right){
			tmp->next = j;
		}
		
		return dummy->next;
	}
	
	void show(Node * head){
		while(head){
			cout << head->val << ",";
			head = head->next;
		}
		cout <<endl;
	}
	
	Node * init(){
		vector<int> init = {4, 3, 2};
		int len = init.size();
		
		Node * head = new Node(init[0]);
		Node * index = head;
		for(int i = 1; i < len; i++){
			Node * tmp = new Node(init[i]);
			index->next = tmp;
			index = index->next;
		}
		return head;
	}
	
	Node * getMid(Node * head, Node * right){
		Node * slow = head;
		Node * fast = head;
		while(fast != right){
			// cout << "fast:" << fast->val << endl;
			slow = slow->next;
			fast = fast->next;
			if(fast != right){
				fast = fast->next;
			}
		}
		return slow;
	}
	
	Node * getLast(Node * head){
		while(head->next){
			head = head->next;
		}
		return head;
	}
};


int main(){
	Solution so;
	Node * head = so.init();
	so.show(head);
	Node * n1 = so.sort(head);
	so.show(n1);
	
	return 0;
}